package com.lhcai.nk;


/**
 * @author lhcstart
 * @create 2023-02-22 22:07
 */

/**
 * kmp算法
 * 描述
 * 给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次
 * 数据范围： 1≤len(S)≤500000,1≤len(T)≤1000000
 * 要求：空间复杂度 O(len(S))，时间复杂度 O(len(S)+len(T))
 */
public class NC149 {
    public static void main(String[] args) {
        NC149 nc = new NC149();

        int kmp = nc.kmp("ababab", "abababab");
        System.out.println(kmp);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 计算模板串S在文本串T中出现了多少次
     *
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp(String S, String T) {
        // write code here
        //特殊情况判断
        int m = S.length(), n = T.length();
        if (m > n || n == 0) {
            return 0;
        }

        int[] next = strNext(S);
        int num = 0;

        for (int i = 0, j = 0; i < T.length(); i++) {

            while (j > 0 && S.charAt(j) != T.charAt(i)) {
                j = next[j - 1];
            }

            if (S.charAt(j) == T.charAt(i)) {
                j++;
            }
            if (j == S.length()) {
                num++;
                j = next[j - 1];
            }
        }
        return num > 0 ? num : 0;
    }

    public int[] strNext(String s) {
        int[] next = new int[s.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < s.length(); i++) {
            //核心点，重置j
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }

            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

}